package com.robert.BCH;

import java.util.ArrayList;
import java.util.List;

public class minPoly {
    /**
     * minPoly是用来计算极小多项式的
     * 下面计算极小多项式每一项的系数，如计算x^5+ax^4+bx^3+..+d中的a,b,c,d
     * combination是排列组合conbinations函数的返回结果
     */
    //List<Integer> combination = new ArrayList<>();//当需要调试combinations函数时启用此行命令
    private List<Integer> combination;


    /**
     * 根据分圆域求极小多项式
     * @param p 公共参数
     * @param a alpha
     * @param l 分圆域
     */
    public int[] minPolynomial(parameters p, alpha a, List<Integer> l){
        int[] ans = new int[l.size()+1];
        ans[0] = 1;
        boolean pm = false; //用于判定系数的正负号，奇数次前面是负号，偶数次是正号
        int lg = a.getValue()[0].length;
        for(int i=1;i<l.size()+1;i++){
            //用组合得到系数对幂次，然后求和就是最终x^{deg-i}前面的系数
            combination = new ArrayList<>();
            combinations(l,i,0,0,new int[i],p.getN());
            //求和结束sumAlpha的结果模p.getMod()后要么全是0，要么前面全是0最后一位是1
            int[] sumAlpha = new int[lg];
            for(int j:combination){
                //由于次数为i对应alpha中的第i-1行，所以需要再模p.getN()
                //但是java的-1模正整数还是-1，所以需要额外处理一下-1的情况
                int index = j-1;
                if(index==-1) index = p.getN()-1;
                int[] ta = a.getValue()[index];
                for(int k=0;k<ta.length;k++){
                    sumAlpha[k] += ta[k];
                }
            }
            //模p.getMod()后要么全是0，要么前面全是0最后一位是1
            // 对sumAlpha最后的位置模p.getMod()
            //如果为1则isOne=true，为0则isOne=false;
            boolean isOne = true;
            if((sumAlpha[sumAlpha.length-1]%p.getMod()) == 0) isOne = false;
            if(isOne) ans[i] = 1;
        }
        return ans;
    }

    /**
     * 对数组的数字进行排列组合，如n=[1,2,3,4],i=2
     * 则combination=[[1,2],[1,3],[1,4],[2,3],[2,4][3,4]]
     * 并对combination的各个部分求和，即combination = [3,4,5,5,6,7]
     * @param n 列表
     * @param i 对列表中的元素组合数
     * @param start start是计数的参数，当start==i时，则求和
     * @param last last记录上一次递归的位置，下一次添加的元素只能是last之后的元素
     * @param ans 临时的数组，用于存放combination=[[1,2],[1,3],[1,4],[2,3],[2,4][3,4]]中的[1,2]这样的内容
     * @param pn 其中pn是模数，也就是combination的各个位置都要模pn，即pn = 5,combination=【3,4,0,0,1,2】
     */
    private void combinations(List<Integer> n,int i,int start,int last,int[] ans,int pn){
        if(start == i){
            int sum = 0;
            for(int j:ans){
                sum += j;
            }
            combination.add(sum%pn);
            return;
        }
        for(int j=last;j<n.size();j++){
            ans[start] = n.get(j);
            combinations(n,i,start+1,j+1,ans,pn);
        }
    }
}
